package hash;

/**
 * 基于拉链法实现的哈希表
 * key和value都存储整型
 */
public class HashMapByLink {
    //实际存储的每个结点,冲突时使用单链表链接冲突的结点
    private class Node {
        int key;
        int value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
        //实际存储的元素个数
        private int size;
        //默认哈希表长度
        private static final int DEFAULT_CAPACITY=4;
        //默认负载因子
        private static final double LOAD_FACTOR=0.75;
        //取模数
        private int M;
        //实际存储Node结点的数组
        private Node[] table;
        public HashMapByLink(){
            this(DEFAULT_CAPACITY);
        }
        public HashMapByLink(int initCap){
            this.table=new Node[initCap];
            this.M=initCap;
        }

    /**
     *向哈希表中添加一个键值对
     * @param key
     * @param value
     * @return 若没有重复元素，返回value，若key已经存在，更新为新的value，返回之前的value3
     */
        public int put(int key,int value){
           // 1.先求key的hash值
            int index=hash(key);
            //2.判断当前哈希表中是否已经存在了这个key，若存在，更新为value，返回旧的value
            for (Node x=table[index]; x!=null;x=x.next) {
                if(x.key==key){
                    int oldValue=x.value;
                    x.value=value;
                    return oldValue;
                }
            }
            //3.此时key不存在，新建一个结点头插入相应的链表中(原链表头结点-table[index]
            Node newNode=new Node(key,value,table[index]);
            //更新原先头结点的指向为当前结点
            table[index]=newNode;
            size++;
            //4.扩容
            if(size>=LOAD_FACTOR*table.length){
                resize();
            }

            return value;
        }

    private void resize() {
            Node[] newTable=new Node[table.length<<1];
            this.M= newTable.length;

        for (int i = 0; i < table.length; i++) {
            Node next=null;
            for (Node cur=table[i];  cur!=null ; cur=next) {
                next=cur.next;
                int newIndex=hash(cur.key);
                cur.next=newTable[newIndex];
                newTable[newIndex]=cur;
            }
        }
        this.table=newTable;
    }

    /**
     * 根据 key值取得相应的value
     * @param key
     * @return
     */
    public int get(int key){
            int index=hash(key);
        for (Node x=table[index]; x!=null ; x=x.next) {
            if(x.key==key){
                return x.value;
            }
        }
        //此时没有找到该元素
        return -1;
    }

    /**
     * 查找key值是否存在
     * @param key
     * @return
     */
    public boolean containsKey(int key){
        int index=hash(key);
        for (Node x=table[index]; x!=null ; x=x.next) {
            if(x.key==key){
                return true;
            }
        }
        return false;
    }

    /**
     * 查找value值是否存在
     * @param value
     * @return
     */
    public boolean containsValue(int value){
        for (Node x:table) {
            for(Node a=x;a!=null;a=a.next){
                if(a.value==value){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除哈希表中指定的键值对
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key,int value){
        int index=hash(key);
        if (table[index] .key== key) {
            //此时头结点就是待删除的结点
           table[index]=table[index].next;
            size--;
            return true;
        }
        //头结点不是待删除的结点
        Node prev=table[index];
        for (Node x=table[index].next; x!=null ; x=x.next) {
            if(x.key==key) {
              prev.next=prev.next.next;
              size--;
              return true;
            }
            prev=prev.next;
        }
        return false;
    }
    //最简单的对key取模
    private int hash(int key){
            return (key & 0xfffffff) % M;
    }
}
